1. Field of the Invention
Embodiments of the present invention relate generally to a flash memory device. More particularly, embodiments of the invention relate to flash memory device and an associated data merge method.
A claim of priority is made to Korean Patent Application No. 2005-10750, filed on Feb. 4, 2005, the disclosure of which is hereby incorporated by reference in its entirety.
2. Discussion of Related Art
Nonvolatile memory can be found in a wide variety of consumer and industrial electronic devices, such as personal computers, personal digital assistants, laptops, cellular phones, and cameras, to name but a few. Nonvolatile memory is particularly useful because of its ability to retain stored data even when power is cut off. One of the more popular forms of nonvolatile memory is flash memory. Some of the advantages of flash memory include its speed of operation, its ruggedness, and low power consumption.
Conventional memory systems such as hard disks and floppy disk drives are not as rugged or power efficient as flash memory because they have moving parts that can be easily damaged. As a result, some conventional computer systems are replacing hard disk drives and floppy drives with flash memories.
Unfortunately, replacing a conventional disk drive with flash memory is not entirely straightforward. One reason is because data stored in a conventional disk drive can be overwritten in its current location, but data stored in a flash memory cannot be overwritten without first erasing an entire block of data. In other words, conventional disk drives have “write in place” capability, whereas flash memory does not. As a result, when a flash memory is required to coordinate with a host system that uses the memory access conventions of a conventional disk drive, the flash memory typically uses a flash translation layer (FTL), which is a driver that reconciles a logical address space used by the operating system with a physical address space used by the flash memory.
The flash translation layer generally performs at least three functions. First, it divides the flash memory into pages that can be accessed by the host system. Second, it manages data stored in the flash memory so that the flash memory appears to have write in place capability, when in reality, new data is written to erased locations of the flash memory. Finally, the flash translation layer manages the flash memory so that erased locations are available for storing new data.
Managing the flash memory involves various operations. For example, whenever a logical address is overwritten, a page of data stored at a corresponding physical address is invalidated and new page of data is stored at a new physical address of the flash memory. Whenever a sufficient number of pages in the flash memory are invalidated, the FTL performs a “merge” operation whereby “valid” pages are transferred from source blocks containing invalid pages to destination blocks with available space. The purpose of the merge operation is to free up memory space occupied by invalidated blocks by erasing the source blocks.
The above operations describe how a FTL typically works. A variety of different address translation schemes are disclosed, for example, in U.S. Pat. No. 5,404,485, U.S. Pat. No. 5,937,425, and U.S. Pat. No. 6,381,176.
A more detailed description of FTL operations is presented below in the context of an electronic device comprising a host system connected to a flash memory. The flash memory comprises a plurality memory cells arranged in a memory cell array. The memory cell array is divided into a plurality of blocks, and each of the blocks is divided into a plurality of pages. The flash memory can be erased a block at a time, and it can be programmed or read a page at a time. However, once programmed, a page must be erased before it can be programmed again.
Within a flash memory, each block is designated by a physical block address, or “physical block number” (PBN) and each page is designated by a physical page address, or “physical page number” (PPN). However, the host system accesses each block by a logical block address, or “logical block number” (LBN) and each page by a logical page address, or “logical page number” (LPN). Accordingly, to coordinate the host system with the flash memory, the FTL maintains a mapping between the logical block and page addresses and corresponding physical block and page addresses. Then, when the host system sends a logical block and page address to the flash memory, the FTL translates the logical block and page address into a physical block and page address.
As mentioned previously, a merge operation is performed to consolidate valid pages within the flash memory, thereby freeing up space where invalid pages are located. When the merge operation is performed, the FTL must maintain correct mappings between physical and logical block and page addresses. A merge operation typically comprises one or more of the following operations: a block mapping operation, a page mapping operation, and a log mapping operation.
An exemplary block mapping operation is described below in relation to FIG. 1. Intuitively, a block mapping operation is simply a mapping of valid data contained in one block onto another block. One reason to perform a block mapping operation is to update a page within the block while maintaining the same relative locations for the pages. In FIG. 1, one page of a block is updated, and then all pages within the block are transferred to another block. When a block mapping operation occurs, a block mapping table keeping track of mappings between logical block numbers and physical block numbers is updated by the FTL.
Referring to FIG. 1, first and second blocks with respective physical block numbers PBN2 and PBN3 each comprise a plurality of pages. Data stored in an math “ith” page of the first block is updated by programming a corresponding “ith” page in the second block with new data while invalidating the “ith” page in the first block. Then, all valid pages in the first block are transferred to the second block. The transfer of the valid pages is denoted in FIG. 1 by the symbol □. Once all pages in the first block have been transferred to the second block, the first block is erased.
FIG. 2 illustrates an exemplary page mapping operation. In a page mapping operation, pages are transferred to different physical page numbers and the FTL updates a page mapping table to keep track of correspondences between logical and physical page numbers. FIG. 2A shows two memory blocks of a flash memory and FIG. 2B shows a page mapping table for the flash memory.
In FIG. 2, first and second program operations have been performed with each of logical page numbers 0 and 1. In the first program operations, logical page number 0 mapped to physical page number 0 and logical page number 1 mapped to physical page number 0. In the second program operations, logical page number 0mapped to physical page number 4 and logical page number 1 mapped to physical page number 3. As a result, pages of data stored at physical page numbers 0 and 1are invalidated, as illustrated by crossed out boxes in FIG. 2A.
To free up the memory space at physical page numbers 0 and 1, the page mapping operation transfers pages of data from a first block with physical block number PBN0 to a second block with physical block number PBN1. As a result, pages of data stored in the first block are stored at new physical page numbers in the second block while keeping the same logical page numbers. Then, once all valid data is transferred from the first block to the second block, the first block is erased.
FIG. 3 illustrates a log mapping operation, wherein pages of data from two different blocks are transferred to a single block. Referring to FIG. 3, a flash memory is divided into a data region, a log region, and a meta region.
The memory block shown in FIG. 3A comprises first through ninth physical memory blocks PBN0 through PBN8. Memory blocks PBN0-PBN4 are located in the data region, memory blocks PBN5-PBN7 are located in the log region, and a memory block PBN8 is defined in the meta region. It is assumed that memory blocks PBN5 and PBN6 in the log region correspond to respective memory blocks PBN0 and PBN2 and memory block PBN8 in the meta region is designated as an empty memory block.
Where the host system initiates a program operation for a page in memory block PBN0, data is programmed in a corresponding page in log block PBN5. However, where the host system initiates a program operation for a page in memory block PBN1, no corresponding block exists in the log region. Accordingly, to create space for a block corresponding to memory block PBN1, memory block PBN5 and PBN0 are merged by a log mapping operation.
In the log mapping operation, as illustrated in FIG. 3B, valid pages in memory blocks PBN5 and PBN0 are transferred to corresponding locations in a memory block PBN7. In the log mapping operation, the FTL maintains a mapping table to keep track of the correspondences between logical and physical addresses of the blocks and pages in the flash memory.
One problem with conventional merge operations is that the host system can not determine when a merge operation occurs, since merge operations are determined by operations of the FTL which are transparent to the host system. Since FTL does not store information about a file system, such as a file allocation table, the FTL can not determine whether the host system considers a page invalid. Accordingly, in some instances, a file system for the host system may mark certain pages for deletion without the awareness of the FTL. As a result, a merge operation performed by the FTL may copy pages that are invalid from the host system's point of view. As a result, the merge operation takes more time than it should, thus degrading the performance of the memory system.